package leetcode.editor.cn.dsa08_hashtable;
//给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

import java.util.ArrayList;
import java.util.List;

public class LongestSubstringWithoutRepeatingCharacters3_1 {
    public static void main(String[] args) {
        Solution solution =
                new LongestSubstringWithoutRepeatingCharacters3_1().new Solution();
        System.out.println(solution.lengthOfLongestSubstring("abcabcbb")); //3
        System.out.println(solution.lengthOfLongestSubstring("dvdf")); //3
        System.out.println(solution.lengthOfLongestSubstring("bbbbb")); //1
        System.out.println(solution.lengthOfLongestSubstring("pwwkew")); //3
        System.out.println(solution.lengthOfLongestSubstring("")); //0
        System.out.println(solution.lengthOfLongestSubstring("abcdefg")); //7
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 解法二：优化解法，使用语言特性
         * 1.定义变量 maxLength 表示最大长度
         * 2.使用双指针截取不含重复字符的子串
         * 3.计算子串长度，保留较大值到 maxLength
         *
         * @param s
         * @return
         */
        public int lengthOfLongestSubstring(String s) {
            int len;
            if (s == null || (len = s.length()) == 0) return 0;
            // 1.定义变量 maxLength 表示最长子串的长度。默认值1
            int maxLength = 1;
            int end = 1;
            // 2.使用双指针截取不含重复字符的子串
            for (int start = 0; start < len; start++) { // 遍历子串的起始字符
                end = end > start + 1 ? end : start + 1;
                for (; end < len; end++) { // 遍历子串的终止字符
                    String substr = s.substring(start, end); // 截取当前字符的前置子串
                    // 当前字符在前面的子串中已出现，该子串到此结束
                    if (substr.indexOf(s.charAt(end)) != -1) {
                        break;
                    }
                }
                // 3.计算子串长度，保留较大值到 maxLength
                int subLen = end - start;
                if (subLen > maxLength) {
                    maxLength = subLen;
                }
                // 如果遍历到结尾了，说明后面的字符都是不重复的，无需继续遍历了
                if (end == len) break;
            }
            return maxLength;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}

